package labuladong.leetcode.editor.cn._01linkedlist.ch00;

import labuladong.leetcode.editor.cn._00bean.ListNode;

import java.util.PriorityQueue;

import static labuladong.leetcode.editor.cn._00utils.LinkedListUtils.build;
import static labuladong.leetcode.editor.cn._00utils.LinkedListUtils.print;

public class _23_MergeKSortedLists {

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            if (lists.length == 0) return null;
            // 虚拟头结点
            ListNode dummy = new ListNode(-1);
            ListNode p = dummy;
            // 优先级队列，最小堆
            PriorityQueue<ListNode> pq = new PriorityQueue<>(
                    lists.length, (a, b) -> (a.val - b.val));
            // 将 k 个链表的头结点加入最小堆
            for (ListNode head : lists) {
                if (head != null)
                    pq.add(head);
            }

            while (!pq.isEmpty()) {
                // 获取最小节点，接到结果链表中
                ListNode node = pq.poll();
                p.next = node;
                if (node.next != null) {
                    pq.add(node.next);
                }
                // p 指针不断前进
                p = p.next;
            }
            return dummy.next;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new _23_MergeKSortedLists().new Solution();

        int[] nums1 = {1, 4, 5};
        ListNode link1 = build(nums1);
        print(link1);

        int[] nums2 = {1, 3, 4};
        ListNode link2 = build(nums2);
        print(link2);

        int[] nums3 = {2, 6};
        ListNode link3 = build(nums3);
        print(link3);

        ListNode[] lists = {link1, link2, link3};

        ListNode res = solution.mergeKLists(lists);
        print(res);
    }
}
